LISP
thumb|Первая лисп-машина в музее [[Массачусетский технологический институт|Массачусетского технологического института.]] Лисп (LISP, от — «язык обработки списков»; современное написание: Lisp) — семейство языков программирования, программы и данные в которых представляются системами линейных списков символов. Создатель Лиспа Джон Маккарти занимался исследованиями в области искусственного интеллекта (в дальнейшем ИИ) и созданный им язык по сию пору является одним из основных средств моделирования различных аспектов ИИ. Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования , а также первый из сохранившихся в использовании языков, использующих автоматическое управление памятью и сборку мусора . Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но начиная уже с ранних версий обладает также чертами императивности, к тому же, имея полноценные средства символьной обработки, позволяет реализовать объектно-ориентированность; примером такой реализации является платформа CLOS. Является языком системного программирования для так называемых лисп-машин, производившихся в 1980-е годы, например, фирмой . Наряду с языком Ада, Лисп прошёл процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ. Архитектура и синтаксис Основные элементы языка Базовыми элементами языка являются символы, атомы и построенные из них динамические списочные структуры — S-выражения. Символ в Лиспе — это объект в машинной памяти, представляющий собой совокупность «слотов» — ячеек, хранящих ссылки. Часть слотов имеет изначально определённое языком назначение: * Имя — строка знаков, по которой программа может ссылаться на данный символ (основополагающее аристотелево А=А, из которого вырастает лямбда-исчисление). * Функциональный слот — лямбда-выражение, связанное с символом. Когда обращение к символу в программе синтаксически соответствует вызову функции, в результате вычисляется лямбда-выражение, связанное с символом. * Значение — объект в машинной памяти, который можно трактовать как данные. Когда программа обращается к символу как переменной, она получает значение данного слота. * Прочие системные слоты, определяемые реализацией. Набор слотов является динамически расширяемым и может, вследствие этого, использоваться как список произвольных свойств символа (можно свободно расширить слотовую систему удобным для решения задачи способом). Такое представление позволяет рассматривать символы как узлы многокоординатной сети, где каждая координата записана в своём слоте. Атомы — это символы и числа. Числа не являются лисповскими символами, поскольку могут иметь только собственное числовое значение и никакого другого. В то же время числа наравне с символами могут входить в списки. Этим и обусловлено объединение этих двух понятий в одну общую категорию. Основная структура данных Лиспа — динамический список атомов, определяемый рекурсивно как головной объект и присоединённый к нему список-хвост. Поскольку голова списка тоже может быть списком, список, фактически, является формой представления произвольного дерева (сам список верхнего уровня — корень, входящие в него подсписки второго и следующих уровней — узлы, атомы — листья). Для атомов и списков язык использует крайне примитивный скобочный синтаксис: символ представляется своим именем, число — записью его значения, а список — в виде заключённой в круглые скобки последовательности списков и атомов, в которой идущие подряд атомы при необходимости разделены пробелами. Список является последовательностью элементов любого рода, в том числе других списков. Например, (1 3/7 'foo #'+) состоит из целого числа, рациональной дроби, символа foo и указателя на функцию сложения. Выражения представляются списками в префиксной записи: первый элемент должен быть формой, то есть функцией, оператором, макросом или специальным оператором; прочие элементы — аргументы этой формы, передаваемые форме для обработки. Арифметические операторы записываются по тому же принципу, например (+ 4 (* 2 3)) выдаёт 10 (в инфиксной записи это 2 * 3 + 4). Синтаксис в форме Бэкуса — Наура: s_expression ::= atomic_symbol | "(" s_expression "." s_expression ")" | list list ::= "(" s_expression { s_expression } ")" atomic_symbol ::= letter atom_part atom_part ::= empty | letter atom_part | number atom_part letter ::= "a" | "b" | " ..." | "z" number ::= "1" | "2" | " ..." | "9" empty ::= " " Характерная особенность программы на Лиспе состоит в том, что абсолютно всё, и данные, и код любой сложности описывается в этом примитивном синтаксисе. Результатов такого подхода два: * Внешне лисп-программа выглядит как гигантское нагромождение скобок. Имеющиеся в любой современной системе средства форматированного вывода, позволяющие отобразить список так, чтобы была видна его структура, несколько исправляют ситуацию, но в целом для восприятия лисп-программ «на глаз» требуется определённый навык. Впрочем, редактирование программ значительно упрощается использованием текстового редактора, поддерживающего автоматическое выравнивание кода, подсветку соответствующих пар скобок и такие специальные команды, как «закрыть все открытые скобки», «перейти через список вправо» и т. д. * Первичный синтаксический разбор лисп-программы и обрабатываемых ею данных может выполняться одним и тем же простейшим кодом, данные могут без каких-либо трудностей обрабатываться в качестве программы, а программа — в качестве данных. Вследствие этого Лисп позволяет легко создавать мощные программы, динамически порождающие код. Лисп-машина способна воспринимать каждый поступающий на неё список на самом абстрактном уровне, например как мета-лисп-машину, модифицирующую воспринимающую машину. В такой динамичной, высокоабстрактной среде можно реализовать как строго научные системы, так и неисчислимое множество программистских трюков и генераторов всевозможных машин. Любая программа на языке Лисп состоит из последовательности выражений (форм). Результат работы программы состоит в вычислении этих выражений. Все выражения записываются в виде списков — одной из основных структур Лиспа, поэтому они могут легко быть созданы посредством самого языка. Это позволяет создавать программы, изменяющие другие программы или макросы, позволяющие существенно расширить возможности языка. Базовые символы, операторы и функции Развитые реализации Лиспа содержат сотни системных функций, макросов и операторов. Здесь приводятся лишь те из них, которые составляют базис работы со списками и создания функциональных программ на Лиспе. ; T и NIL : Встроенные символы-константы Лиспа, обозначающие логическую истинность и ложность соответственно. Значения T и NIL возвращают логические операторы и операторы и функции сравнения. : Помимо этого у символа NIL есть ещё одно значение — он может обозначать пустой список. ; LIST : Эта функция возвращает список своих аргументов: : (list 1 3/7 'foo) >> (1 3/7 'foo) : (здесь и далее в примерах >> означает, что в результате вычисления левой части интерпретатор Лиспа выдаёт то, что находится справа) : Если аргументов нет, возвращается пустой список: : (list) >> NIL : Если некоторые элементы являются выражениями, то сначала вычисляется их значение: : (list 1 2 (list 1 2)) >> (1 2 (1 2)). ; QUOTE : Системный оператор QUOTE подавляет вычисление своего аргумента. Если он не используется, то интерпретатор Лиспа, получив на входе список или символ, пытается его вычислить: для символа возвращается его значение, для списка — результат вызова функции, имя которой находится в голове списка, с параметрами — хвостом списка. Если же нужно, чтобы интерпретатор не вычислял значения, а взял символ или список «как есть», к нему применяют QUOTE. : (LIST 1 2 (QUOTE(LIST 1 2))) >> (1 2 (LIST 1 2)) : (QUOTE (list 1 2 (list 1 2))) >> (LIST 1 2 (LIST 1 2)) : Поскольку подавление вычислений — очень частая операция, имеется сокращающий её запись синтаксический сахар — вместо полной формы вызова QUOTE можно просто поставить перед выражением апостроф: : (LIST 1 2 '(LIST 1 2)) >> (1 2 (LIST 1 2)). ; EVAL : Эта функция, по сути, и есть интерпретатор Лиспа. Являясь противоположностью QUOTE, она вычисляет значение своего аргумента. : (EVAL '(LIST 1 2 '(LIST 1 2))) >> (1 2 (LIST 1 2)) : (EVAL '(LIST 1 2 (EVAL'(LIST 1 2)))) >> (1 2 (1 2)) : Возможность прямого и непосредственного вызова интерпретатора вкупе с идентичностью структуры программы и данных позволяет без каких-либо ограничений порождать и непосредственно исполнять в системе любые лисп-программы. ; CAR : Возвращает голову списка: : (CAR '(A B C D)) >> A : (CAR '((A B)(C D))) >> (A B) : Специальный случай: : (CAR NIL) >> NIL : Формально в чистом функциональном программировании значение головы пустого списка является неопределённым, но в Лиспе (по крайней мере, в большинстве диалектов) принято соглашение, по которому и голова, и хвост пустого списка равны NIL. ; CDR : Возвращает хвост списка: : (CDR '(A B C D)) >> (B C D) : (CDR '((A B)(C D))) >> ((C D)) : Следует обратить внимание, что в последнем случае возвращается список в списке: хвост аргумента является списком из одного элемента, который, в свою очередь, сам является списком из двух элементов. : (CDR NIL) >> NIL ;C*R : Здесь на месте звёздочки «*» в имени функци может стоять от 2 до 4 букв «A» и «D» в любых комбинациях. То есть возможны функции CDDDDR, CADAR, CADDR и так далее. Вызов такой функции эквивалентен вложенному вызову соответствующего набора функций CAR и CDR, например, (CADAR '((A B C) D E F)) соответствует (CAR (CDR (CAR '((A B C) D E F)))) и вернёт значение «B». Необходимость в подобных странных функциях связана с часто повторяющейся задачей: извлечь из списка определённый элемент, положение которого известно. ; CONS : Принимает в качестве аргумента голову и хвост и создаёт из них список или точечную пару, если аргументы являются атомами: : (CONS 'A '(B C D)) >> (A B C D) — присоединение атома к списку; : (CONS '(A B) '((C D))) >> ((A B) (C D)) — добавление списка к голове другого списка; : (CONS 'A 'B) >> (A . B) — создание точечной пары из двух атомов. ; COND : Обобщённая условная конструкция. Имеет вид: : (COND ((Условие1)(Выражение1)) ((Условие2)(Выражение2)) …) : Последовательно вычисляются Условие1, Условие2 и так далее до тех пор, пока очередное УсловиеN не окажется истинным (станет иметь значение T). Тогда будет выполнено соответствующее ВыражениеN и его значение будет возвращено в качестве значения вызова COND. Если истинного условия не будет найдено, COND вернёт значение NIL. Обычной практикой является ставить в качестве последнего условия в COND значение T, гарантируя тем самым, что при невыполнении всех остальных условий будет вычислено последнее из выражений; так создаётся аналог ветви ELSE условных операторов императивных языков программирования. ; DEFUN : Конструкция, позволяющая определить функцию. Общий (упрощённый) формат определения следующий: : (DEFUN Имя (Параметр1 Параметр2 …) Выражение1 Выражение2 …) : Здесь Имя — имя функции. Соответствующий символ, если его ещё нет, будет создан в системе и в его функциональный слот запишется определение функции. В дальнейшем интерпретатор Лиспа, встретив Имя в голове вычисляемого списка, интерпретирует его как вызов данной функции с перечисленными в хвосте параметрами. Параметр1 и так далее — имена формальных параметров функции. : Последовательность Выражение1, Выражение2 и так далее — это последовательность вычислимых выражений, в которых могут использоваться Параметры и глобальные переменные системы. При вызове функции Выражения вычисляются последовательно и в качестве значения функции будет возвращено значение, вычисленное последним по порядку выражением. Специальные операторы позволяют управлять последовательностью вычислений. С их помощью реализуются ветвления и циклы. Оператор if позволяет вычислить одно из двух выражений в зависимости от выполнения условия, которое тоже является выражением. Если его результат не ЛОЖЬ (не nil), то вычисляется первый аргумент, иначе — второй. Например, (if nil (list 1 2 "foo") (list 3 4 "bar")) всегда возвращает (3 4 "bar"). Парадигмы программирования в Лиспе Лисп изначально проектировался как функциональный язык программирования с отдельными императивными чертами, введёнными из соображений удобства практического использования. Однако вскоре выяснилось, что выбранный формализм и набор примитивов, на которых базируется язык, дали возможность расширения его в самых различных направлениях. За десятилетия эксплуатации и развития языка он вобрал в себя практически все существующие методологии программирования и на настоящий момент может считаться одним из мощнейших мультипарадигменных языков высокого уровня. Функциональное программирование Функциональная парадигма является для Лиспа «родной», поскольку основой архитектуры его является лямбда-исчисление Чёрча. Собственно, именно с Лиспа началось функциональное программирование как практическая методология разработки программного обеспечения. Лямбда-выражения являются в Лиспе полноправными языковыми объектами, допускающими не только непосредственный вызов, но и присваивание, сохранение в качестве значения символа, передачу в качестве параметра вызова и возврат в качестве результата. Таким образом, Лисп поддерживает функционалы, то есть функции, принимающие в качестве параметров и возвращающие в результате другие функции. В разных диалектах Лиспа подход к характеру функций как языковых объектов несколько различается. В Common Lisp функция и лямбда-выражение представляют собой отдельную категорию программных объектов, для которых существуют специфические правила и ограничения; в частности, это выражается в том, что у символа имеются раздельные слоты для значения и для функции, связанной с этим символом, и в этом смысле функция — это не вполне то же самое, что элемент данных. В других диалектах, таких как T-Lisp или Scheme, функции являются так называемыми «полноправными гражданами» — могут без ограничений присваиваться переменным, передаваться в качестве параметров вызова и возвращаться как результаты вызова. Современный стандарт Лиспа — Common Lisp, — вызывает нарекания сторонников «чистого» функционального программирования тем, что не все его функциональные средства являются теоретически «чистыми». Это действительно так, поскольку Common Lisp разрабатывался как универсальный промышленный язык, и в ряде случаев соображениям практической целесообразности сознательно отдавалось предпочтение перед соображениями теоретической чистоты. Тем не менее, Лисп был и остаётся функциональным языком программирования. Императивное (операторное) программирование Исходно в синтаксис Лиспа заложена возможность описания алгоритмов путём перечисления последовательности требуемых действий. Она заключается в так называемом «неявном PROGN», поддерживаемом в структуре лямбда-вызовов Лиспа: в том месте, где должна размещаться команда, составляющая основу лямбда-выражения, может быть записано не одна, а несколько команд, и результатом лямбда-вызова станет результат последней из них. Таким образом, Лисп поддерживает неявное последовательное исполнение операций. Помимо неявного PROGN, поддерживаются явные императивные механизмы императивного программирования: * Конструкции PROG1 и PROGN — обеспечивают выполнение команд последовательно. * LET — позволяет задать локальные переменные блока и выполнить с ними последовательные операции. * Все виды циклов. * Конструкции присваивания SET, SETF, SETQ, выполняющие присваивания. * Ряд системных структуроразрушающих функций (выполняющих операции с данными «на том же месте»). В Common Lisp особое место занимает системный макрос LOOP. Он позволяет создать в лисп-программе фрагмент, написанный на языке программирования с привычной императивной структурой и инфиксной записью операторов. Макропрограммирование Простейшим средством макропрограммирования, доступным в любой реализации Лиспа, является возможность непосредственного вызова интерпретатора (функции EVAL) с передачей ему любой списочной структуры в качестве программы. Это позволяет программе верхнего уровня выступить в качестве макрогенератора, то есть сформировать исполняемый код, который будет впоследствии исполнен. Однако эта возможность используется редко из-за своей громоздкости. Гораздо чаще используется система макросов Лиспа. Современные варианты Лиспа, в том числе стандарт Common Lisp, обладают развитыми возможностями создания и использования макросов. Описание макроса в Лиспе синтаксически подобно описанию функции (разница состоит только в использовании ключевого слова defmacro вместо defun в описании), но поведение макроса существенно отличается: каждый вызов макроса «раскрывается» в момент трансляции программы, порождая код, который на этапе исполнения выполняется так, как будто был непосредственно написан в месте вызова. Ещё одним отличием макросов от обычных функций является то, что их аргументы по умолчанию не вычисляются. Кроме того, ряд реализаций Лиспа поддерживает создание так называемых «макросов чтения» — макросов, непосредственно преобразующих текст программы. Макросы позволяют прозрачно определять новые языковые конструкции и даже дополнять синтаксис языка. Последняя возможность активно используется при реализации на Лиспе исходно не поддерживаемых в нём методов и средств программирования. Объектно-ориентированное программирование Лисп не является изначально объектно-ориентированным языком. Сама парадигма объектно-ориентированного программирования на полтора десятка лет моложе Лиспа, тем не менее, когда она появилась и доказала свою полезность, объектные возможности были добавлены и в этот язык. При этом сразу же обнаружилось, что набор базовых возможностей Лиспа делает добавление в него объектно-ориентированной подсистемы не только возможным, но и простым. Лисп, благодаря наличию в языке свойств (слотов) у символов изначально поддерживает инкапсуляцию. Функциональные свойства Лиспа (поддержка функционалов, присваивание функций переменным и сохранение их в свойствах символов) дают возможность связывать код (методы) с данными (объектами). Наконец, динамический характер языка в сочетании с вышеперечисленными особенностями обеспечивает полиморфное поведение коду и данным в лисп-программе. Единственный компонент ООП-системы, которого нет в базовом Лиспе — наследование, но и оно реализуется без всяких затруднений. Таким образом, Лисп изначально содержит в себе все элементы, на которых базируется технология ООП, и реализация поддержки этой технологии в языке сводится, по сути, лишь к созданию соответствующих синтаксических средств. Благодаря развитому механизму макроописаний ООП-синтаксис в Лисп может быть добавлен средствами самого языка, без необходимости расширения базового синтаксиса и модификации трансляторов. Простой и элегантный пример создания собственной ООП-подсистемы в Лиспе можно найти в книге Пола Грэма «ANSI Common Lisp». Среди промышленных известных объектно-ориентированных расширений Лиспа прежде всего следует назвать объектную подсистему Flavors, которая была включена в состав системы Зеталисп. Эта подсистема обеспечивала объявление классов (flavors — «ароматов»), единичное и множественное наследование, полиморфные методы классов, Smaltalk-подобную систему взаимодействия объектов путём передачи сообщений (фактически реализованную как вызов методов объекта). Другим примером может служить LOOPS (Lisp Object-Oriented Programming System) — объектная подсистема, реализованная в 1983 году в диалекте Интерлисп. Объектная система CLOS (Common Lisp Object System), первоначально созданная в дополнение к Common Lisp, а позже вошедшая в стандарт языка, подобна Flavors и поддерживает принципиально тот же набор возможностей, стандартный для почти любого современного объектно-ориентированного языка. Применение объектно-ориентированного программирования в Лиспе, в основном, связано с решением задач моделирования и/или управления, которые по своему характеру удачно совмещаются с объектно-ориентированной технологией. Например, одним из первых приложений системы Flavors было взаимодействие с многооконным интерфейсом пользователя, который как раз удобно моделировать в виде набора объектов, обменивающихся сообщениями. История Предпосылки Автором Лиспа является Джон Маккарти, на период создания языка работавший в Массачусетском технологическом институте (MIT) в должности профессора по связи. Вместе с Марвином Мински он занимался работами по искусственному интеллекту, в связи с чем и возникла потребность в создании языка программирования, адекватного задачам, решаемым в этой области. Работа по созданию языка была проделана Маккарти в MIT в период с 1958 по 1963 год, после чего он перешёл в Стенфордский университет в Калифорнии, где получил должность «профессор по искусственному интеллекту». Основой для Лиспа послужил ранний язык IPL, разработанный Ньюэллом, Шоу и Саймоном. IPL был языком обработки списков и предназначался для реализации проекта «Логик-теоретик» — системы искусственного интеллекта, предназначенной для автоматического вывода теорем математической логики. IPL был довольно низкоуровневым языком, но в нём уже были реализованы такие базовые идеи, как единый механизм хранения программ и данных в виде списков — иерархических структур элементов, связанных ссылками (сама идея списочного представления знаний была позаимствована из исследований по психологии и ассоциативной памяти), а также идея динамического распределения памяти. После ознакомления в 1956 году с IPL у Маккарти появилась идея реализовать обработку IPL-списков в Фортране, который как раз в это время проектировался в IBM (причём под ту же систему IBM 704, с которой Маккарти работал в MIT), но эта идея так и не была реализована. Позже Маккарти принял участие в работе «комитета по языку высокого уровня», разрабатывавшему Алгол, но и там его предложения были встречены холодно. В результате Маккарти пришёл к мысли о необходимости создания нового языка программирования. Первоначально Маккарти сформулировал списочный формализм для описания данных (S-выражения) и основанный на нём же механизм описания лямбда-выражений, что позволило записывать программы в виде наборов функций, представленных в списочной форме. Как писал позже Маккарти, изначально он планировал применять для записи программ отдельный формализм, отличающийся от S-выражений, но это оказалось излишним. Когда с помощью своей списочной записи Маккарти описал алгоритм функционирования интерпретатора нового языка (формализм, который впоследствии стал известен как «Лисп на Лиспе»), Стив Рассел заметил, что теперь для создания реального работающего интерпретатора достаточно просто перевести эту запись в машинный код. Маккарти отнёсся к этой идее скептически, но Рассел действительно проделал данную работу и получил первый интерпретатор Лиспа для компьютера IBM 704. В дальнейшем идея написания транслятора языка на нём самом многократно использовалась, и не только в функциональных и логических языках, но и в императивных. Первые реализации Исторически первой реализацией Лиспа, включающей все современные базовые элементы языка, был интерпретатор, работавший на IBM 704, появившийся в октябре 1958 года. Это, кстати, позволяет говорить о Лиспе как об одном из двух старейших языков высокого уровня, которые находятся в употреблении с момента создания до настоящего времени (первый — Фортран). Помимо этого, Лисп сохранил первенство ещё в одном отношении. Дело в том, что активная работа с динамическими списками сделала невозможным ручное управление памятью, которое в императивных языках отчасти сохраняется по сей день. Создание новых списочных ячеек и списков и выход из использования имеющихся при работе лисп-программы происходят настолько активно, что практически невозможно обойтись без системы автоматического управления памятью, которая контролировала бы использование ранее созданных в памяти объектов и периодически удаляла те из них, использование которых прекратилось, то есть системы сборки мусора. Маккарти пришлось реализовать эту систему, благодаря чему Лисп, помимо прочего, является ещё и самым старым из применяемых сегодня языков программирования с автоматическим управлением памятью и сборкой мусора. Позднее были созданы реализации для IBM 7090, в дальнейшем — для серий IBM 360 и 370. Компьютеры IBM оказались неудобны для работы в интерактивном режиме, вследствие чего в конце 1950-х годов небольшая группа разработчиков, в том числе работавших ранее в IBM, выделилась в самостоятельную компанию Digital Equipment Corporation (DEC). Первым её изделием стал компьютер PDP-1, изначально ориентированный на интерактивный режим работы. На этой машине в 1960 году была реализована интерактивная система «Lisp 1», включающая в себя интегрированные интерпретатор, редактор исходного кода и отладчик, позволявшая выполнять весь цикл работ над программой непосредственно в системе. По сути, это была первая «среда программирования» в том смысле, который вкладывается в это понятие сейчас. Тогда же в журнале «Communications of ACM» вышла статья Маккарти «Recursive Functions of Symbolic Expressions and their Computation by Machine.», в которой Лисп был описан в виде алгебраического формализма на самом Лиспе. Статья стала классической, а формализм типа «Лисп на Лиспе» с тех пор стал одним из наиболее употребимых в литературе по теории программирования. Ещё одним технологическим новшеством, появившимся в связи с реализацией системы «Lisp 1» был изобретённый Маккарти механизм, позволявший запускать интерпретатор Лиспа одновременно с выполнением обычных вычислительных работ в пакетном режиме (то, что сейчас известно как «система разделения времени»). К 1962 году была готова следующая версия оригинальной лисп-системы «Lisp 1.5», в которой были устранены обнаруженные за время эксплуатации недостатки первой версии. Её описание было выпущено в издательстве «MIT Press» в виде отдельной книгиMcCarthy J., Abrahams P., Edwards D., et al. Lisp 1.5 Programmer’s Manual. MIT Press, Cambrige, Massachusetts, 1962.. Поскольку руководство включало описание реализации системы, оно стало основой для создания лисп-систем для множества других компьютеров как в США, так и за её пределами. Основные диалекты Несмотря на использование, подчас весьма активное, Лиспа в европейских и азиатских странах и создание там собственных лисп-систем, большинство распространённых диалектов Лиспа происходят из США. MacLisp С начала 1960-х годов в MIT был запущен проект MAC, в рамках которого велись исследования использования вычислительных машин в интерактивном режиме и разработка подходящих для такой работы языков программирования и операционных систем. MacLisp (далее Маклисп) был разработан в рамках этого проекта, основой для него стала система Lisp 1.5. В 1964 году была создана первая реализация Маклиспа для PDP-6, в 1968 — для PDP-10, причём последняя работала как под управлением операционной системы ITS, разработанной в лаборатории искусственного интеллекта MIT, так и под ОС TOPS-10/20 — стандартной ОС для PDP-10/20 фирмы DEC. Также была создана реализация для компьютера GE-600, работавшая под управлением ОС Multics. Маклисп был чрезвычайно мощной для своего времени системой. На её облике отразилось всё многообразие задач, которые решались в проекте MAC и вообще в исследованиях по искусственному интеллекту в MIT. Помимо традиционных задач символьной обработки, Маклисп использовался для разработок в самых разных областях. Так, работы в области робототехники и обработки речи и изображений потребовали от системы высокой чисто вычислительной эффективности, а также привели к реализации широкого набора математических типов данных, в том числе векторов, матриц и битовых полей. В систему были включены арифметические типы и операции с неограниченной точностью (базирующиеся на алгоритмах, разработанных Д. Кнутом), позволяющие в ряде случаев существенно упростить решение некоторых математических задач, пусть и за счёт значительных вычислительных затрат. Была реализована мощная библиотека математических функций. В части вклада в развитие самого языка можно отметить появившиеся в Маклиспе макросы чтения и таблицы чтения, позволившие «достраивать» язык, расширяя его в нужном направлении новыми структурами. Также в язык были включены средства обработки исключений и средства параллельной обработки. Маклисп стал первой лисп-системой, для которой был реализован высокоэффективный компилятор (до этого лисп-системы не могли похвастаться высокой вычислительной производительностью и отчасти по этой причине сформировалось отношение к Лиспу как к «языку для учёных, а не для промышленности»). Причём эффективность трансляции была достигнута за счёт применения специфически лисповских методов: исходная программа транслировалась в промежуточную машинно-ориентированную форму, имеющую вид лисповских списков (так называемая LAP — List Assembly Program). Машинный код в этой форме путём формальных преобразований подвергался оптимизации, в результате которой результирующая объектная программа для вычислительных задач оказывалась, как правило, более эффективна, чем аналогичная программа на Фортране, оттранслированная лучшими фортрановскими компиляторами для той же платформы. Исторически наиболее известные результаты проекта MAC — это система символьных вычислений Macsyma и текстовый редактор Emacs. Macsyma — мощная система символических вычислений, по сути — пионер в этой области компьютерных систем, разработка её велась в MIT с 1968 по 1982 год. Система была целиком написана на Маклиспе и была, по всей видимости, самой большой широко известной программой в мире, целиком написанной на Лиспе. Именно перенос Macsyma на другие аппаратные и программные платформы стал тем мотивом, который вызвал появление нескольких диалектов Лиспа. Emacs изначально был написанным целиком на Маклиспе полноэкранным текстовым редактором, являющимся как частью среды разработки Маклиспа, так и используемым отдельно от неё, зачастую для целей, не имеющих ничего общего с программированием. Отличительной особенностью его была возможность программирования поведения редактора и добавления в него новой функциональности путём написания соответствующего кода на внутреннем языке, которым стал Emacs Lisp. Фактически ядро редактора представляет собой интерпретатор Emacs Lisp, и некоторый набор системно-зависимых сервисов. Основная часть редактора написана на самом Emacs Lisp. Впоследствии, при переносе Emacs на микрокомпьютеры, ядро было переписано на C (из соображений эффективности — на тот момент не существовало эффективных реализаций Лиспа для ПК), но в остальном редактор остался прежним и продолжил развиваться в том же направлении, приобретя со временем огромное количество написанных на Emacs Lisp дополнений, расширивших его функциональность до огромных размеров, что стало поводом для шутки: «Emacs — отличная операционная система, которой не хватает только приличного текстового редактора». Система MAC Lisp эксплуатировалась и развивалась вплоть до 1980-х годов, оказав существенное влияние на появлявшиеся в 1960—1980 годах реализации Лиспа, в том числе став одним из источников проектирования стандарта Common Lisp. Эксплуатация системы практически прекратилась в 1980-х годах вместе с прекращением использования компьютеров PDP-10/20, на которых она изначально базировалась. Намного пережили систему разработанные на Маклиспе и уже упоминавшиеся Macsyma и Emacs. Interlisp Разработкой лисп-систем в середине 1960-х годов занимались многие компании и исследовательские центры в США. Интерлисп (Interlisp) стал результатом объединения усилий BBN (Bolt, Beranek and Newman Inc.), SDS (Scientific Data Systems) и Xerox. Исследовательский центр BBN в 1966 году приступил к созданию своей реализации Лиспа, ориентированной на компьютеры PDP-10 и SDS-930. Версия BBN-Lisp для PDP использовала аппаратный механизм страничной организации памяти и переключения контекста, созданный специально для обеспечения высокоэффективного разделения времени. BBN-Lisp стал популярен среди исследователей в области искусственного интеллекта и во многом способствовал тому, что именно машины PDP-10/20 вплоть до 1980-х годов оставались основными инструментами в работах по ИИ. В начале 1970-х корпорация Xerox купила обанкротившуюся SDS и начала сотрудничать с BBN. Несмотря на то, что машины SDS не имели большого коммерческого успеха, реализация Лиспа от BBN была достаточно перспективной, чтобы Xerox поддержала её дальнейшую разработку, в результате чего BBN-Lisp превратился в Interlisp (Интерлисп). А в 1974 году в Xerox началась разработка персональной рабочей станции Alto, исходно ориентированной на Лисп. В этой системе впервые была произведена разработка аппаратуры и системы машинных команд под конкретный язык программирования. На основе Интерлиспа была создана упрощённая версия системы Interlisp-D, предназначенная для лисп-машин серии 1100 («потомков» станции Alto). В этих машинах был впервые реализован многооконный графический интерфейс пользователя, использована графика с высокой разрешающей способностью и применён манипулятор «мышь». Интерлисп был тщательно разработанной и хорошо документированной системой. Он представлял собой хорошо продуманную интегрированную среду разработки с редактором исходных кодов, отладчиком, интерпретатором и множеством вспомогательных инструментов разработчика. В этом смысле его можно считать классическим примером развитой программной среды для систем разделения времени. В системных библиотеках было реализовано свыше 500 функций, система имела большое количество настроек, позволявших «подогнать» её под пользователя. Реализации Интерлиспа со временем были выполнены на большинстве широко распространённых больших компьютеров, работавших в режиме разделения времени. Что же касается собственно языка, то можно заметить, что диалект со всеми его характерными особенностями был зафиксирован уже в середине-конце 1970-х годов, после чего кардинальных изменений в язык не вносилось. Это привело к некоторому отставанию системы от более новых разработок в части функциональности и к фиксации некоторых устаревших проектных решений. Вследствие этого уже к началу 1980-х Интерлисп испытывал трудности как с совместимостью с новыми системами, так и с дальнейшим расширением. Наиболее существенные недостатки Интерлиспа — отсутствие иерархии типов данных, объектов и замыканий (впрочем, в 1983 году в Интерлиспе была реализована объектная система LOOPS, дающая возможности объектно-ориентированного программирования). Более существенно то, что Интерлисп базируется на динамическом связывании, тогда как все новые версии Лиспа — статические. PSL Лисп попал в Калифорнию вместе с Маккарти, перешедшим в Стенфорд в 1963 году. За следующие несколько лет были разработаны системы Lisp 1.6 (прямой потомок «классического» Lisp 1.5), UCI Lisp (University of California, Irvine) и Stanford Lisp/360. Оттуда вместе с Энтони Хёрном Лисп попал в в Университет штата Юта, где занималась исследованиями в области символьной математики в приложениях теоретической физики. Хёрн предложил решать эти задачи с помощью Лиспа, в результате чего в 1968 году была создана система компьютерной алгебры Reduce. Хёрн в 1966 году опубликовал спецификацию Standard Lisp, которую предлагал в качестве основы для стандартизации языка. Предложение его не встретило поддержки, так как не было одобрено исследователями искусственного интеллекта, указавшими на ряд нежелательных для них особенностей предлагаемого стандарта, в частности, излишнюю привязку к типам. Тем не менее, на основе данной спецификации в Юте был реализован Portable Standard Lisp — PSL. Эта реализация была использована для развития Reduce и переноса её на различные аппаратные платформы. Специально для улучшения переносимости в PSL был включён сокращённый набор системных функций и структур. Реализация была основана на промежуточном низкоуровневом лисп-подобном языке SYSLisp; ядро PSL было написано на SYSLisp, а вся остальная часть системы — на самом PSL. Для PDP-10 был реализован транслятор SYSLisp и написанный на том же SYSLisp кросс-компилятор, с помощью которого ядро PSL можно было перенести на любую другую аппаратуру. С помощью этой технологии PSL и Reduce были реализованы на целом ряде платформ, в том числе на DEC-10/20, VAX/UNIX, HP9000, Apollo, Wicat, IBM, Cray. Таким образом, PSL стал одним из первых примеров реализации техники «раскрутки» при переносе программных систем на новую архитектуру, когда для переноса системы ядро изначально пишется на машинно-независимом промежуточном языке, для которого, в свою очередь, создаются реализации на всех целевых платформах. Дальнейшее сопровождение PSL осуществлялось исследовательским центром фирмы Hewlett-Packard в Калифорнии. Franz Lisp Мотивом для создания в конце 1970-х годов системы Franz Lisp послужило желание получить лисп-систему для новых компьютеров VAX, чтобы обеспечить выполнение на них системы Macsyma и другого написанного на Лиспе программного обеспечения. Поскольку основной целью был перенос Macsyma, за основу был взят MACLisp, однако из языка были исключены некоторые устаревшие особенности и добавлены новые механизмы, заимствованные из разрабатываемого в то время в том же MIT Zetalisp. Наиболее значительный вклад в создание данного диалекта внесли Университет Беркли, Университет Пенсильвания, Bell Labs, Ливерморская национальная лаборатория и Университет Карнеги-Меллона. Одним из основных вдохновителей проекта был профессор Университета Беркли Ричард Фэйтман, ранее работавший в MIT и участвовавший в разработке оригинальной системы Macsyma. В числе создателей Franz Lisp было несколько его учеников. Название системы было выбрано в честь известного венгерского композитора Ференца Листа (английское написание: Franz Liszt). Система была реализована в 1981 году на C для VAX 780/11 под управлением ОС UNIX. Входящий в состав системы компилятор носил имя «Liszt» — фамилии композитора, давшего имя диалекту. В 1982 году система была портирована на процессор Motorola 68000, затем ещё на ряд 32-разрядных персональных платформ, в результате она стала наиболее широко используемой версией Лиспа как для 32-разрядных систем с разделением времени, так и для 32-битовых мини-ЭВМ и персональных рабочих станций. Система Franz Lisp распространялась бесплатно под лицензией BSD, но аспирант Университета Беркли Фридрих Кунце подал идею создания коммерческой компании, которая бы обеспечивала качественную платную поддержку пользователей и выполняла заказы по портированию Franz Lisp на новые аппаратные и программные платформы. Это было время активного роста компьютерного рынка и перспективы выглядели неплохо. Компания была зарегистрирована в 1984 году и получила название «Franz Inc». Начало деятельности фирмы было достаточно удачным, ей удалось получить контракт на портирование Franz Lisp на платформу Sun, а позже — ещё несколько аналогичных предложений. Однако в 1985 году под давлением Министерства обороны США американское лисп-сообщество начало активную переориентацию на новый диалект — Common Lisp, создание которого в это время завершалось. В этих условиях Franz Inc. не могла найти новых контрактов, оказалась на грани закрытия и была вынуждена перейти к разработке собственной реализации Common Lisp — Allegro Common Lisp (название было выбрано, чтобы сохранить преемственность «музыкальной» темы). История Franz Lisp на этом, фактически, завершилась. В настоящее время оригинальная система полностью вышла из употребления. Scheme Язык Scheme был разработан в 1976 году в MIT в рамках проекта по созданию лисп-машины — персональной рабочей станции, разработанной полностью, начиная с аппаратуры, в расчёте на максимально эффективное использование языка Лисп. Исходно Scheme был всего лишь «исследовательским языком», в ходе разработки которого опробовались различные идеи и методы. Ставилась цель обеспечить минимальный набор базовых возможностей, который обеспечивал бы построение полноценной лисп-системы путём надстраивания этого набора. В результате получилось небольшое по объёму и элегантно определённое ядро, при этом весьма эффективно реализованное. В частности, Scheme стал первым диалектом Лиспа, в котором гарантировалась оптимизация хвостовой рекурсии. В языке реализован мощный механизм макросов, помимо списков в качестве базовых конструкций поддерживаются массивы. Характерное синтаксическое отличие Scheme от большинства диалектов Лиспа — немного другая форма определения функции. Если в большинстве диалектов используется вариант: (DEFUN ИмяФункции (Аргументы) Выражения), то в Scheme сокращённая форма определения выглядит как (DEFINE (ИмяФункции Аргументы) (Выражения)). (Различается ключевое слово и взаимное расположение имени функции и аргументов). Scheme — единственный диалект Лиспа (не считая встроенных вариантов, таких как Emacs Lisp или AutoLISP), который продолжает использоваться после повсеместного перехода лисп-сообщества на стандартизованный Common Lisp. В настоящее время существует несколько поддерживаемых реализаций Scheme, в том числе свободных, есть примеры использования этого языка и в качестве встроенного (например, используемый в качестве средства создания скриптов GIMP Tiny-Scheme). В нескольких американских университетах Scheme используется как язык для базового обучения программированию. Zetalisp Zetalisp или «Lisp Machine Lisp» был создан в MIT во второй половине 1970-х годов в рамках проекта лисп-машины, профинансированного американским оборонным агентством DARPA. Со стороны собственно языка Зеталисп был основан на Маклиспе и редакторе Emacs, но существенно обновлён и дополнен, в частности, в нём появились новые типы данных, объектно-ориентированная подсистема Flavors, на которой основано взаимодействие программ с многооконным интерфейсом пользователя, новые директивные управляющие конструкции, частично заимствованные из Интерлиспа, многозначные функции (способные штатным образом возвращать более одного значения без предварительной «сборки» их в контейнер), потоковый ввод-вывод, пространства имён, мощная библиотека функций, в том числе математических, обеспечивающих векторные и матричные вычисления и работу с линейными системами. Гораздо больше новшеств было внесено в саму систему программирования. Система изначально рассчитывалась на работу с графическим пользовательским терминалом и мышью. В ней был реализован графический многооконный интерфейс пользователя. В состав системы входил многооконный интерпретатор Лиспа, частичный транслятор, текстовый редактор Zmacs, инспектор структур данных, отладчик, программа исследования состояния системы, редактор системных файлов, редактор шрифтов и клиент электронной почты Zmail. В состав системы входили трансляторы других языков высокого уровня, преобразователь, обеспечивающий поддержку программ на Интерлиспе, и набор инструментов более высокого уровня. Для Фортрана, Паскаля, Ады и Пролога, поставлявшихся в составе системы, имелись развитые средства взаимодействия с программами на Лиспе, что позволяло в случае необходимости разрабатывать и применять программные системы на нескольких языках. Изначально проект имел целью создание коммерческого продукта. В 1979 году было создано два предприятия — производителя лисп-машин: Symbolics и Lisp Machine Inc. (LMI). После этого работа по развитию Зеталиспа велась этими фирмами независимо. Тем не менее, при наличии некоторых различий в самих лисп-машинах, в части языка они были почти полностью совместимы. NIL и T Реализация MACLisp на машине VAX в самом MIT была начата в 1979 году. Проект получил название NIL (одновременно — аббревиатура «New Implementation of Lisp» — «Новая реализация Лиспа» — и стандартный лисповский атом «NIL», обозначающий, в зависимости от использования, логическую не-истинность или пустой список). NIL имел довольно большое ядро, написанное на ассемблере VAX, на котором всё тем же методом раскрутки строилась лисп-система. В какой-то мере можно считать NIL «ответом на Franz Lisp», поскольку в качестве одной из целей проекта был назван всё тот же перенос на VAX системы Macsyma. NIL много позаимствовал у Зеталиспа, в том числе систему Flavors, превращающую Лисп-систему в объектно-ориентированную. В 1981 году группа, занимавшаяся проектом NIL, распалась из-за непримиримых разногласий в отношении идеологии создаваемой системы. Несмотря на распад, начиная с 1982 года выходили регулярные обновления системы и она получила достаточно заметное распространение. В 1980-е годы NIL нередко использовался в организациях, имевших как VAX, так и лисп-машины, поскольку принципиальных идеологических отличий между NIL и Zetalisp нет, хотя Zetalisp намного богаче возможностями. Отделившаяся от проекта NIL группа разработчиков приступила к созданию собственной версии лисп-системы, которая получила ироничное имя «T» (одновременно — от «True Lisp» — «Настоящий (истинный) Лисп» и ещё один стандартный лисповский атом «T», обозначающий логическую истинность, то есть — противоположность «NIL»). Разработка этого диалекта велась в Йельском университете в 1982—1984 годы. В отличие от «старых» систем, диалект T использовал по умолчанию статическое связывание переменных, кроме того, его создатели ввели реализацию функций как «полноправных граждан», что означает, что функции могут без специальных синтаксических средств и без ограничений присваиваться переменным и возвращаться в качестве значений других функций. T-Lisp, в отличие от NIL, имел довольно небольшое ядро, написанное на машинном языке. Разработчики использовали технику «раскрутки», перенося ядро вручную на новые платформы и реализуя остальную часть системы непосредственно на Лиспе, рассчитывая, что высокоэффективный транслятор обеспечит лучшую производительность конечной системы, чем ручная реализация крупного ядра на машинном языке. Спорным моментом в T-Lisp стало решение авторов обновить и систематизировать имена системных функций. Так, например, имена всех без исключения предикатов оканчивались на вопросительный знак, «исторически сложившиеся» стандартные имена элементарных функций были заменены на мнемонические, соответствующие тому, что функция делает. Безусловным плюсом такого решения было облегчение изучения, очевидным минусом стала несовместимость со всеми остальными диалектами языка. В результате создателям всё равно пришлось впоследствии дополнить систему набором макросов, приводящих систему имён в соответствие со стандартом Common Lisp. Безусловно значительное влияние, которое на T оказал диалект Scheme. В целом же T-Lisp получился достаточно простой, элегантной и мобильной системой, которая была реализована для VAX и перенесена на многие 32-битовые рабочие станции. Стандарт Common Lisp Процесс разработки стандарта Из вышесказанного ясно, что к первой половине 1980-х годов в лисп-сообществе сложилась ситуация, которую некоторые авторы сравнивали с Вавилонской башней: параллельно существовали и развивались более десятка только крупных диалектов Лиспа, общее же число несовместимых между собой реализаций было существенно больше. Похожая ситуация наблюдалась в это время в большинстве распространённых языков программирования, в случае же с Лиспом ситуация усугублялась тем, что язык изначально был разработан как произвольно расширяемый, что спровоцировало развитие его возможностей в разных диалектах в существенно разных направлениях. Если на начальном этапе, когда Лисп использовался почти исключительно в лабораториях и институтах, многообразие диалектов не особенно мешало и даже было отчасти полезным, поскольку способствовало быстрому развитию языка, то к 1980-м годам, когда появилась потребность в промышленных разработках на Лиспе, обилие реализаций стало тормозом, поскольку приводило к массовому дублированию разработок и рассредоточению сил на поддержание множества лисп-систем в актуальном состоянии. Попытки стандартизации Лиспа предпринимались и ранее, почти с момента его появления (первое предложение по стандартизации Лиспа датируется 1960 годом), но из-за разобщённости и значительных различий в интересах заинтересованных групп разработчиков ни одно из предложений не было принято. Дело сдвинулось с мёртвой точки лишь тогда, когда в качестве организатора процесса стандартизации выступила могущественная и богатая государственная организация — Министерство обороны США. Во второй половине 1970-х годов им была проведена огромная работа по анализу ситуации в программных разработках военного назначения и, затем, по поддержке создания на конкурсной основе нового языка высокого уровня для встроенных систем, которым стал язык Ада. Однако Ада изначально не предназначалась для искусственного интеллекта и символьной обработки и совершенно не приспособлена для решения такого рода задач. Поэтому, объявив Аду основным языком, обязательным для разработок по военным заказам, для ИИ-приложений и близких к ним задач военное ведомство США оказалось вынуждено допустить к использованию более подходящий для этих целей язык. Поэтому Министерство обороны США оказало организационную и финансовую поддержку формированию промышленного стандарта языка Лисп, который и приняло в качестве дополнительного средства разработки ПО для военных применений. Первоначальный вариант стандарта начали готовить в Университете Карнеги-Меллона на основе внутреннего проекта Spice Lisp, также первоначально нацеленного на разработку лисп-системы для рабочей станции. Проектируемый стандарт с самого начала получил наименование «Common Lisp» («Общий Лисп»), подчёркивающее цель разработки — получить единый базовый язык, на основании которого можно было бы создавать программно-совместимые системы. В разработке и редактировании стандарта приняли участие около 80 специалистов из университетов, лабораторий и фирм США. Процесс разработки впервые происходил дистанционно, через компьютерную сеть ARPANET, через которую было передано свыше 3000 сообщений. Процесс разработки стандарта завершился в 1984 году. Его результат был зафиксирован в первом издании руководства «Common Lisp: the Language» Гая Стила. Основные особенности В основном на идеологические основы стандарта повлияли MACLisp и его диалекты, большое количество возможностей было заимствовано из InterLISP и новых систем, таких как Zetalisp и NIL. Common Lisp — язык со статическим связыванием, традиционным представлением функций (функции не являются «полноправными гражданами»), поддерживает макросы, функционалы, лексические замыкания. То есть с точки зрения функциональной части языка он содержит весь тот набор синтаксических средств, который за предыдущие четверть века сложился в Лиспе и достаточен для любых приложений функционального программирования и расширения языка в любом желаемом направлении. Системные функции в Common Lisp сохранили традиционные имена, но многие из них имеют синонимы с более наглядными именами, например, функции CAR (получение головы списка) и CDR (получение хвоста списка) имеют синонимы, соответственно, FIRST («первый») и REST («остаток»). Поскольку разработчикам требовался язык, пригодный для широкого спектра применений, а не только для искусственного интеллекта и символьной обработки, в результате получилась достаточно объёмная спецификация, хотя и сохранившая основные особенности Лиспа, но существенно расширенная функциями, синтаксическими средствами и механизмами, направленными на нехарактерные для исходного Лиспа способы разработки. Так, например, в язык были добавлены практически все существующие в традиционных императивных языках синтаксические конструкции, включая несколько видов циклов. Объектная система CLOS (Common Lisp Object System) первоначально не была включена в стандарт, но вошла в него позже. Common Lisp пригоден для написания программ как в функциональном, так и в директивном стиле, на нём возможно обобщённое программирование (посредством стандартных макросов), продукционное программирование, имеются средства для организации логического, объектного программирования и программирования, управляемого данными. Спецификация Common Lisp не включает в себя подробного описания среды программирования, определяя лишь в самых общих чертах её состав и принципы взаимодействия элементов. Критики нового стандарта указывали на его раздутость и чрезмерное внимание, уделённое практическим требованиям, что привело к нарушению «функциональной чистоты» Лиспа и увеличению объёма поддерживающих его Лисп-систем. Тем не менее, под нажимом Министерства обороны США и частично с его финансовой поддержкой во второй половине 1980-х годов были созданы Common Lisp-реализации практически для всех распространённых платформ. «Старые» Лисп-системы, в большинстве, продолжали существовать, но их поддержка постепенно прекращалась, а пользователи и ПО мигрировали на Common Lisp. В результате к настоящему времени из ранее существовавшего набора реализаций языка в использовании остался разве что диалект Scheme и некоторое количество встроенных в мощное ПО систем, в которых Лисп играет роль скриптового языка для реализации внутренней логики и расширения возможностей. Дальнейшие модификации Серьёзный пересмотр вышедшего в 1984 году стандарта, состоялся в 1990 году, когда в него были внесены существенные изменения: * Объектная система CLOS, исходно не входившая в спецификацию Common Lisp, а считавшаяся неким «дополнением» к ней, стала частью официального стандарта * Был стандартизован макрос loop, реализующий встроенный императивный язык с инфиксным синтаксисом. * Внесены изменения в типы данных. * Стандартизован механизм pretty-print — форматированного вывода кода и данных. * Введены макросы компиляции. * Добавлены новые операторы и внесены изменения в существующие. * Обновлена система поддержки пакетов. * Сделан ряд более мелких изменений. В 1995 году Common Lisp был стандартизован ANSI. Стандарт практически повторил спецификацию 1990 года, изменения незначительны и состоят, в основном, в добавлении, удалении и переименовании операторов и системных переменных и изменениях в системных вызовах. Можно отметить появление в Common Lisp типа boolean (логического), значениями которого могут быть только NIL и T. Примеры Пример программы, выводящей сообщение «Hello, world!»: (format t "Hello, world!~%") Пример Куайн (программы, выводящей свой исходный код) на Лиспе: ((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x)))) Данная программа должна работать на большинстве диалектов Лиспа, в том числе и на Scheme. Итеративная версия функции определения N-го числа Фибоначчи с использованием макроса Loop: (defun fibonacci (n) (loop repeat n for a = 0 then b and for b = 1 then (+ a b) finally (return b))) Рекурсивная версия функции N-го числа Фибоначчи: (defun fibonacci (n) (if (> n 1) (+ (fibonacci (1- n)) (fibonacci (- n 2))) n)) Рекурсивная функция вычисления произвольной целой степени: (defun power (m n) (cond ((= n 1) m) ((zerop n) 1) ((minusp n)(/ 1 (power m (- n)))) (t (* m (power m (1- n)))))) Здесь использованы системные предикаты ZEROP — проверка на равенство нулю, MINUSP — проверка на отрицательность. Применение Первые области применения языка Лисп были связаны с символьной обработкой данных и процессами принятия решений. Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с реляционными и объектными базами данных, научные расчёты и игровые программы. Одно из направлений использования языка Lisp — его использование в качестве скриптового языка, автоматизирующего работу в ряде прикладных программ: * язык Лисп используется как язык сценариев в САПР AutoCAD (диалект AutoLISP); * его диалект — SKILL — используется для написания скриптов в САПР Virtuoso Platform компании Cadence Design Systems; * язык Лисп является одним из базовых средств текстового редактора Emacs (диалект EmacsLISP)По сути, большая часть Emacs написана на EmacsLISP, что даёт неограниченные возможности расширения функциональности; * язык Лисп используется как язык сценариев в издательском программном обеспечении Interleaf/Quicksilver (диалект Interleaf Lisp); * в оконном менеджере Sawfish применяется специальный диалект Лиспа Rep, который в значительной степени повторяет диалект Лиспа от Emacs; * диалект Scheme используется в качестве одного из скриптовых языков в графическом процессоре Gimp; * диалект GOAL используется для высокодинамичных трёхмерных игр; * язык Лисп может использоваться для написания скриптов в аудиоредакторе Audacity. Сферы применения языка Лисп многообразны: наука и промышленность, образование и медицина, от декодирования генома человека до системы проектирования авиалайнеров. Лисп-машины В начале 1970-х годов были осознаны ограничения, накладываемые системой разделения времени на пользователей интерактивных программных средств (к которым относятся и Лисп-системы, и большинство написанных на Лиспе программ). Кроме того, для Лиспа оказались относительно велики затраты на программную динамическую поддержку, включающую проверку типов во время исполнения и периодическую сборку мусора. Усложняющиеся программы требовали более производительного оборудования, и в 1973 году возникла идея разработки компьютера индивидуального пользования (рабочей станции), спроектированной, начиная с оборудования, специально для достижения максимально эффективного исполнения Лисп-программ, в том числе с аппаратной поддержкой лямбда-вычисления и динамической типизации. В США исследования по созданию Лисп-компьютера велись в 1970-х годах в двух местах — исследовательском центре Palo Alto, принадлежащем корпорации Xerox, и в MIT (последнее спонсировалось DARPA). Результатом стало появление в начале-середине 1980-х годов трёх основных производителей: Xerox, Lisp Mashine Inc. (LMI) и Symbolics Inc. Xerox производил Лисп-машины, поддерживающие Интерлисп, две последние компании происходят из MIT и ориентируются на Зеталисп. Несколько позже производством Лисп-машин занялась Texas Instruments, а в Японии в 1984 году был показан первый прототип коммерческой Лисп-машины Alpha фирмы Фудзицу. Лисп-машины имели аппаратную архитектуру, ориентированную на обработку списков и функциональное программирование, с аппаратной поддержкой сборки мусора, динамической типизации. Поддерживаемые этими машинами комплексы средств разработки ПО представляли собой мощные интегрированные среды разработки, включающие в себя все компоненты, которые в настоящее время включают наиболее мощные IDE языков высокого уровня. Поддерживался многооконный графический интерфейс пользователя, работа с мышью и другими дополнительными средствами позиционирования (трэкбол, световое перо), высококачественный ввод-вывод графики и звука. Несмотря на изначальную Лисп-ориентированность, в Лисп-машинах были доступны и другие языки высокого уровня и предоставлялись средства межъязыкового взаимодействия. Сами Лисп-системы Лисп-машин содержали до тысяч функций различного назначения, обеспечивали как работу в интерпретируемом режиме, так и компиляцию программ в объектный код. Для своего времени Лисп-машины были одними из мощнейших ЭВМ в классе персональных рабочих станций. Им прочили большое будущее, но в 1990-х годах все они вышли из употребления. Производители либо прекратили свою деятельность, либо переориентировались на выпуск компьютеров общего назначения. Причиной стало то, что в условиях длительного экспоненциального роста скорости и объёмов памяти компьютеров разработка оборудования «под язык» оказалась бесперспективной — быстро развивающиеся компьютеры общего назначения, снабжённые трансляторами Лиспа, по своим возможностям догнали и обогнали специализированные Лисп-машины, которые из-за самой специализации уже оказывались дороже и проигрывали в универсальности. Лисп в СССР и России В СССР работы, связанные с использованием Лиспа и созданием собственных Лисп-систем активизировались после 1968 года, когда группа американских учёных, среди которых были Дж. Маккарти и Б. Беркли, посетила Советский Союз. В Новосибирске, в ВЦ Сибирского отделения Академии Наук, где Маккарти провёл больше всего времени, он заложил основу реализации Лиспа на БЭСМ-6. В Москве, в ВЦ АН СССР советские математики Лавров и Силагадзе при содействии Беркли начали работу над собственной версией Лисп-интерпретартора для БЭСМ-6. Впоследствии Лавров перешёл на работу в ЛГУ, а Силагадзе — в ВЦ Грузинской академии наук в Тбилиси, где они продолжили работу с Лиспом и участвовали в создании нескольких Лисп-систем для ЕС ЭВМ. В Ленинграде была создана Лисп-система для польского компьютера Odra 1204, в Москве — реализация для БЭСМ-6, совместимая с английской версией Лиспа для компьютера ICL 4, в МЭИ и в Дальневосточном научном центре во Владивостоке появились реализации для ЕС ЭВМ. В Институте проблем передачи информации (Москва) в конце 1970-х была создана Лисп-система ЭКЛИСП для мини-компьютера ECLIPS. На компьютерах западного производства в СССР использовались Stanford Lisp и UT-Lisp (Дубна, IBM 370 и CDC 6600). Также популярна была шведская система Нордстрема (Лисп на Фортране). В 1975 году в Тбилиси состоялась четвёртая международная конференция по проблемам искусственного интеллекта IJCAI-75, которая способствовала повышению интереса к Лиспу и распространению его в университетах и НИИ. В 1978 году вышел первый учебник Лиспа на русском языке: С. С. Лавров и Г. С. Силагадзе «Автоматическая обработка данных. Язык ЛИСП и его реализация». В 1980-е годы интерес к Лиспу в СССР сохранялся, тем не менее, литературы по языку издавалось очень мало (за десятилетие вышло две книги, обе переводные: «Функциональное программирование. Применение и реализация» Хендерсона, переведённая в 1983 году, и двухтомник «Мир Лиспа» Э. Хювёнена и Й. Сеппянена, перевод которой был издан в 1990). После распада СССР российское IT-сообщество достаточно быстро перешло на использование практически исключительно западной вычислительной техники и системного ПО. На сегодняшний день невозможно назвать ни одной Лисп-системы российского происхождения, которая находилась бы в эксплуатации. Лисп нельзя назвать популярным или распространённым в России; его использование в основном ограничивается академическими исследованиями и работами отдельных энтузиастов. Кроме того, Лисп продолжает использоваться в учебных целях в некоторых российских университетах, но и здесь в последние годы он оказался заметно потеснён: как язык общего назначения он не преподаётся и не используется, а в качестве учебных языков для преподавания функционального программирования часто предпочитают использовать более молодые функциональные языки, появившиеся в последние два десятилетия. Тем не менее, интерес к языку сохраняется, свидетельством чего является появление переводных и оригинальных печатных работ по Лиспу, возобновившееся в последние годы. Интересные факты * Существуют альтернативные расшифровки названия LISP: Lots of Irritating Superfluous ParenthesesThe Jargon File — Lisp («Много раздражающих лишних скобок») — намёки на особенности синтаксиса. * Системные функции CAR и CDR получили такие необычные имена по историческим причинам. Машина IBM 704, на которой Маккарти создавал самую первую реализацию Лиспа, содержала инструкции, позволяющие модифицировать части машинного слова. Машинное слово рассматривалось как структура с полями префикса, декремента, тега и адреса. Функции CAR (сокращение от Contents of the Address part of Register — «содержимое адресной части регистра») и CDR (Contents of the Decrement part of Register — «содержимое декрементной части регистра») получили свои названия в соответствии с этими полями . В этой реализации поля адреса и декремента использовались для хранения, соответственно, указателей на голову и хвост списка. См. также * NewLISP Примечания Литература * Х. Абельсон, Д. Сассман. Структура и интерпретация компьютерных программ. — Книга и курс лекций MIT. В качестве основного языка используется Scheme. * *: Перевод: * * Peter Seibel. . * Ссылки * pcl.catap.ru — русский перевод книги en:Practical Common Lisp * Cookbook — русский перевод (незаконченный) сборника рецептов Common Lisp Cookbook * lisp.ru — ресурсы по языку Лисп (учебники, статьи). * lisper.ru — сайт, посвящённый Common Lisp, написанный на самом Common Lisp * lisp.ystok.ru — Лисп у «Истоков» (литература, ссылки, проекты с исходным кодом) ; Ссылки на английском: * www-formal.stanford.edu — статья Джона Маккарти Recursive Functions of Symbolic Expressions and Their Computation by Machine, содержащей первоначальное описание языка Лисп. * gigamonkeys.com — сайт книги en:Practical Common Lisp, откуда может быть скачана электронная версия (pdf) и архив с исходными кодами для книги * Cliki — вики-ресурс о библиотеках и проектах Common Lisp. Примечательно, что сам ресурс написан полностью на Common Lisp. * common-lisp.net — основной хостинг Common Lisp проектов. * lisp.org — ассоциация пользователей Лисп * Архивы списков рассылки на Gmane. *